/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._10_01;

import java.math.BigInteger;

/**
 *
 * 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
 *
 * F(0) = 0,   F(1) = 1
 * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 * 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
 *
 * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 2
 * 输出：1
 * 示例 2：
 *
 * 输入：n = 5
 * 输出：5
 *  
 *
 * 提示：
 *
 * 0 <= n <= 100
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._10_01
 * @ClassName: Fib
 * @Author: linyaonan
 * @Date: 2020/4/3 14:46
 */
public class Fib {

    public int fib(int n) {
        BigInteger fib = getFib(n);
        return fib.mod(BigInteger.valueOf(1000000007L)).intValue();
    }

    public int fib2(int n) {
        if (n <= 1) {
            return n;
        } else {
            int[] ints = new int[n];
            ints[0] = ints[1] = 1;
            for (int i = 2; i < ints.length; i++) {
                ints[i] = (int) ((ints[i-1] + ints[i-2]) % 1000000007L);
            }
            return ints[n-1];
        }
    }

    private BigInteger getFib(int n) {
        if (n <= 1) {
            return BigInteger.valueOf(n);
        } else {
            BigInteger[] ints = new BigInteger[n];
            ints[0] = BigInteger.ZERO;
            ints[1] = BigInteger.ONE;
            for (int i = 2; i < ints.length; i++) {
                ints[i] = ints[i-1].add(ints[i-2]);
            }
            return ints[n-1];
        }
    }

}
